/**
 * 2116.判断一个括号字符串是否有效.ts
 */

function canBeValid(s, locked) {
  const length = s.length;
  // 如果长度是奇数，直接返回 false
  if (locked.length !== length || length % 2 !== 0) return false;

  // 从左到右遍历
  let open = 0,
    close = 0;
  for (let i = 0; i < length; i++) {
    if (locked[i] === '0') {
      // 可以变为 '(' 或 ')'
      open++;
      close++;
    } else if (s[i] === '(') {
      // 固定为 '('
      open++;
      close++;
    } else {
      // 固定为 ')'
      open--;
      close--;
    }
    // 如果 close < 0，说明右括号过多，无法匹配
    if (close < 0) return false;
    // 确保 open 不会小于 0
    open = Math.max(open, 0);
  }

  // 从右到左遍历
  (open = 0), (close = 0);
  for (let i = length - 1; i >= 0; i--) {
    if (locked[i] === '0') {
      // 可以变为 '(' 或 ')'
      open++;
      close++;
    } else if (s[i] === ')') {
      // 固定为 ')'
      open++;
      close++;
    } else {
      // 固定为 '('
      open--;
      close--;
    }
    // 如果 open < 0，说明左括号过多，无法匹配
    if (open < 0) return false;
    // 确保 close 不会小于 0
    close = Math.max(close, 0);
  }

  // 如果两次遍历都通过，则返回 true
  return true;
}

// 测试用例
console.log(canBeValid('))()))', '010100')); // true
console.log(canBeValid('()()', '0000')); // true
console.log(canBeValid(')', '0')); // false
console.log(canBeValid('(((())(((())', '111111010111')); // true
